package sharewithus.analyzer.utils;

import java.util.List;


/**
 * 三叉逆词典树
 * 
 * @author terry
 * 
 * @param <T>
 */
public class TernaryInverseTrie<T> {

	private TSTNode<T> root;

	public void add(String key, T val) {
		TSTNode<T> currentNode = getOrCreateNode(key);
		currentNode.data = val;
	}

	public T find(String key) {
		TSTNode<T> currentNode = getNode(key);
		if (currentNode == null) {
			return null;
		}
		return currentNode.data;
	}

	public TSTNode<T> getOrCreateNode(String key) {
		if (key == null) {
			throw new NullPointerException(
					"attempt to get or create node with null key");
		}
		if ("".equals(key)) {
			throw new IllegalArgumentException(
					"attempt to get or create node with key of zero length");
		}
		int charIndex = key.length() - 1; // 当前要比较的字符在查询词中的位置
		char currentChar = key.charAt(charIndex); // 当前要比较的字符
		if (root == null) {
			root = new TSTNode<T>(currentChar);
		}
		TSTNode<T> currentNode = root;
		while (true) {
			// 比较词的当前字符与节点的当前字符
			int compa = currentChar - currentNode.splitChar;
			if (compa == 0) { // 词中的字符与节点中的字符相等
				charIndex--;
				if (charIndex < 0)
					return currentNode;

				currentChar = key.charAt(charIndex);
				if (currentNode.mid == null)
					currentNode.mid = new TSTNode<T>(currentChar);

				currentNode = currentNode.mid; // 向下找
			} else if (compa < 0) { // 词中的字符小于节点中的字符
				if (currentNode.left == null)
					currentNode.left = new TSTNode<T>(currentChar);

				currentNode = currentNode.left; // 向左找
			} else { // 词中的字符大于节点中的字符
				if (currentNode.right == null)
					currentNode.right = new TSTNode<T>(currentChar);

				currentNode = currentNode.right; // 向右找
			}
		}
	}

	public TSTNode<T> getNode(String key) {
		TSTNode<T> currentNode = root; // 匹配过程中的当前节点的位置
		int charIndex = key.length() - 1; // 当前要比较的字符在查询词中的位置
		char currentChar = key.charAt(charIndex); // 当前要比较的字符
		int charComp;
		while (true) {
			if (currentNode == null) {// 没找到
				return null;
			}
			// 比较查询词中的字符与节点中的字符
			charComp = currentChar - currentNode.splitChar;
			if (charComp == 0) {// 查询词中的字符与节点中的字符相等
				charIndex--;
				if (charIndex < 0) {// 找到了
					// System.out.println("find node:"+currentNode.nodeValue);
					return currentNode;
				}
				currentChar = key.charAt(charIndex);
				currentNode = currentNode.mid;
			} else if (charComp < 0) {// 查询词中的字符小于节点中的字符
				currentNode = currentNode.left;
			} else {// 查询词中的字符大于节点中的字符
				currentNode = currentNode.right;
			}
		}
	}

	/**
	 * 匹配英文
	 * 
	 * @param start
	 *            开始位置
	 * @param sentence
	 *            文本
	 * @return 开始位置
	 */
	public int matchEnglish(int end, String sentence) {
		int i = end;
		// int count = sentence.length();
		String sd = "ＱＷＥＲＴＹＵＩＯＰＡＳＤＦＧＨＪＫＬＺＸＣＶＢＮＭ号";
		while (i >= 0) {
			char c = sentence.charAt(i);
			if (c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z') {
				--i;
			} else if (sd.indexOf(c) > -1) {
				--i;
			} else {
				break;
			}
		}
		return i;
	}

	/**
	 * 匹配数字
	 * 
	 * @param end 开始位置
	 * @param sentence 文本
	 * @return 开始位置
	 */
	public int matchNum(int end, String sentence) {
		int i = end;
		while (i >= 0) {
			char c = sentence.charAt(i);
			if ((c >= '0' && c <= '9') || (c >= '０' && c <= '９') || c == '-'
					|| c == '－' || c == '#' || c == '号' || c == '＃') {
				--i;
			} else {
				break;
			}
		}
		return i;
	}

	public void matchAll(String sentence, int offset ,List<MatchRet<T>> matchRets) {
		//List<MatchRet<T>> matchRets = new LinkedList<MatchRet<T>>();
		matchRets.clear();
		if (sentence == null || root == null || "".equals(sentence)
				|| offset >= sentence.length()) {
			return;
		}

		int ret = offset;

		ret = matchNum(offset, sentence);
		
		if (ret < offset) {
			MatchRet<T> matchRet = new MatchRet<T>(ret, sentence.substring(ret + 1,
					offset + 1), null);
			matchRets.add(matchRet);
		}

		int retEnglishNum = matchEnglish(offset, sentence);
		if (retEnglishNum < ret) {
			ret = retEnglishNum;
			MatchRet<T> matchRet = new MatchRet<T>(ret, sentence.substring(ret + 1,
					offset + 1), null);
			matchRets.add(matchRet);
		}
		//System.out.println(ret);
		TSTNode<T> currentNode = root;
		int charIndex = offset;
		while (true) {
			if (currentNode == null) {
				return;
			}
			int charComp = sentence.charAt(charIndex) - currentNode.splitChar;

			if (charComp == 0) {
				charIndex--;

				if (currentNode.data != null) {
					ret = charIndex;
					MatchRet<T> matchRet = new MatchRet<T>(ret, sentence.substring(
							ret + 1, offset + 1), currentNode.data);
					matchRets.add(matchRet);
				}
				if (charIndex < 0) {
					return;
				}
				currentNode = currentNode.mid;
			} else if (charComp < 0) {
				currentNode = currentNode.left;
			} else {
				currentNode = currentNode.right;
			}
		}
	}
	
	public void matchAll(String sentence, int offset, T unknowData ,List<MatchRet<T>> matchRets) {
		//List<MatchRet<T>> matchRets = new LinkedList<MatchRet<T>>();
		matchRets.clear();
		if (sentence == null || root == null || "".equals(sentence)
				|| offset >= sentence.length()) {
			return;
		}

		int ret = offset;

		ret = matchNum(offset, sentence);
		
		if (ret < offset) {
			MatchRet<T> matchRet = new MatchRet<T>(ret, sentence.substring(ret + 1,
					offset + 1), unknowData);
			matchRets.add(matchRet);
		}

		int retEnglishNum = matchEnglish(offset, sentence);
		if (retEnglishNum < ret) {
			ret = retEnglishNum;
			MatchRet<T> matchRet = new MatchRet<T>(ret, sentence.substring(ret + 1,
					offset + 1), unknowData);
			matchRets.add(matchRet);
		}
		//System.out.println(ret);
		TSTNode<T> currentNode = root;
		int charIndex = offset;
		while (true) {
			if (currentNode == null) {
				if (matchRets.size() == 0)
					matchRets.add(new MatchRet<T>(offset-1, sentence.substring(offset,
							offset + 1), unknowData));
				return;
			}
			int charComp = sentence.charAt(charIndex) - currentNode.splitChar;

			if (charComp == 0) {
				charIndex--;

				if (currentNode.data != null) {
					ret = charIndex;
					MatchRet<T> matchRet = new MatchRet<T>(ret, sentence.substring(
							ret + 1, offset + 1), currentNode.data);
					matchRets.add(matchRet);
				}else{
					//System.out.println("cnm.." +currentNode);
				}
				if (charIndex < 0) {
					if (matchRets.size() == 0)
						matchRets.add(new MatchRet<T>(offset-1, sentence.substring(offset,
								offset + 1), unknowData));
					return;
				}
				currentNode = currentNode.mid;
			} else if (charComp < 0) {
				currentNode = currentNode.left;
			} else {
				currentNode = currentNode.right;
			}
		}
	}
	
	public MatchRet<T> matchLong(String sentence, int offset, T unknowData){
		MatchRet<T> matchRet = null;
		if (sentence == null || root == null || "".equals(sentence)
				|| offset >= sentence.length()) {
			return matchRet;
		}
		int ret = offset;
		ret = matchNum(offset, sentence);
		if (ret < offset) {
			matchRet = new MatchRet<T>(ret, sentence.substring(ret + 1,
					offset + 1), unknowData);
			return matchRet;
		}

		int retEnglishNum = matchEnglish(offset, sentence);
		if (retEnglishNum < ret) {
			ret = retEnglishNum;
			matchRet = new MatchRet<T>(ret, sentence.substring(ret + 1,
					offset + 1), unknowData);
			return matchRet;
		}
		
		TSTNode<T> currentNode = root;
		int charIndex = offset;
		while (true) {
			if (currentNode == null) {// 当前节点为空,说明词典中找不到对应的词,则将单个字符返回
				/*return new MatchRet<T>(ret, sentence.substring(offset,
						offset + 1), null);*/
				return matchRet == null ? new MatchRet<T>(ret, sentence.substring(offset,
						offset + 1), unknowData): matchRet;
			}
			int charComp = sentence.charAt(charIndex) - currentNode.splitChar;

			if (charComp == 0) {
				charIndex--;
				if (currentNode.data != null) {
					ret = charIndex;
					matchRet = new MatchRet<T>(ret, sentence.substring(
							ret + 1, offset + 1), currentNode.data);
				}
				if (charIndex < 0) {
					return matchRet; // 已经匹配完
				}
				currentNode = currentNode.mid;
			} else if (charComp < 0) {
				currentNode = currentNode.left;
			} else {
				currentNode = currentNode.right;
			}
		}
	}
}
